/*
题目: 二叉树的垂序遍历
给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的 垂序遍历 序列。

https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree
 */
public class VerticalTraversal {
    List<List<Integer>> result = new ArrayList<> ();

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        LinkedList<int[]> list = new LinkedList<> ();

        dfs(root, 0, 0, list);

        Collections.sort(list, new Comparator<int[]> () {
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) { //如果列不相等
                    return o1[0] - o2[0];
                } else if (o1[1] != o2[1]) { //如果行不相等
                    return o1[1] - o2[1];
                } else {
                    return o1[2] - o2[2];
                }
            }
        });

        while (!list.isEmpty()) {
            List<Integer> level = new ArrayList<> ();
            int prevCol = list.peekFirst()[0];
            while (!list.isEmpty() && prevCol == list.peekFirst()[0]) { //列相等
                int[] array = list.pollFirst();
                level.add(array[2]);
                prevCol = array[0];
            }
            result.add(level);
        }

        return result;
    }

    private void dfs(TreeNode root, int row, int col, LinkedList<int[]> list) {
        if (root == null) {
            return;
        }
        dfs(root.left, row + 1, col - 1, list);
        list.add(new int[] {col, row, root.val});

        dfs(root.right, row + 1, col + 1, list);
    }
}
